// 易于理解版
function quickSort1(arr){
    if(arr.length < 2) return arr
    // 基准数
    const base  = arr[0]
    // 辅助数组  较大  相等  较小
    const arrS = [],arrM = [],  arrL = []  ;
    for (const el of arr){
        if(el > base){
            arrL.push(el);
        }
        if(el === base){
            arrM.push(el);
        }
        if(el < base){
            arrS.push(el);
        }
    }
//递归 对较大 较小的数组进行三分操作
    return [...quickSort1(arrS),...arrM,...quickSort1(arrL)]

}
//  不使用辅助数组，需要记住数组的下标范围 参数l r
//  不直接选第一个元素作为基准 在 左中右三个数中取中位数
// 拆分只每个微元数组只有两个元素时就可停止 减少递归层数
function quickSort2(arr, l, r){
    if (r -l < 1) return 
    let x = l, y = r , base = arr[l]
    // 两端往中间围剿啊
    while(x < y) {
        // 右边的值不小于基准值 不用动
        while(x< y && arr[y] >=base){
            y--
        }
        // 此时 arr[y]是右边第一个小于基准值的 应该去左边
        if (x< y){
            arr[x++] = arr[y]
            // arr[x] = arr[y]
            // x++
        }
        // 左边的值不大于基准值 不用动
        while(x< y && arr[x] <= base){
            x++
        }
            // 此时 arr[x]是左边第一个大于基准值的 应该去右边
        if (x < y){
            arr[y--] = arr[x]
        }
      

    }
    // 此时x === y 该把base放回去了
    arr[x] = base 
    // 递归
    quickSort2(arr, l,x-1)
    quickSort2(arr, x+1, r)

    return
}

// 合并有序数组
function  merge(arr1,arr2){
    const res = []
    const [len1, len2] = [ arr1.length ,arr2.length ]
    let [i,j] = [0,0]
    while(i < len1 || j < len2){
        if ((arr1[i] < arr2[j] || i>=len1 )&& j < len2){
            res.push(arr[i++])
        }else {
            res.push(arr[j++])
        }
    }
}
// 真有点微积分的感觉 归并排序
 function mergeSort(arr,l,r){
    if (l => r) {
        return
    }
    let mid = (l +r) >>1 ;

    mergeSort(arr, l,mid)
    mergeSort(arr, mid+1, r)

   let arr3 =  []
   const [len1, len2] = [ mid +1,r +1 ]
   let [i,j] = [0,0]
   while(i < len1 || j < len2){
       if ((arr[i] < arr[j] || i>=len1 )&& j < len2){
           arr3.push(arr[i++])
       }else {
           arr3.push(arr[j++])
       }
   }
    for (let i  = l;i<= r;i++){
        arr[i] = arr3[i-l]
    }
}

function getRandArr(n) {
    const arr = []
    for (let i = 0; i < n; i++) {

        arr.push(Math.random() * 2 * n | 0);
    }
    return arr

}

const arr1 = getRandArr(10) 
console.log(arr1);
mergeSort(arr1,0,9)
console.log(arr1);

// console.log(quickSort1(arr1))